Graph / Plane graph (Bibtex)

P255: Enumeration of all plane straight-line graphs on a given point set in the plane

Input:

A point set $P$ in the plane.

Output:

All plane straight-line graphs on $P$.

Complexity:

$O(|P|\log|P|)$ time per solution.

Comment:

Use gray code.

Reference:

[Aichholzer2007] (Bibtex)

P256: Enumeration of all plane and connected straight-line graphs on a given point set in the plane

Input:

A point set $P$ in the plane.

Output:

All plane and connected straight-line graphs on $P$.

Complexity:

$O(|P|\log|P|)$ time per solution.

Comment:

Use gray code.

Reference:

[Aichholzer2007] (Bibtex)

P257: Enumeration of all plane spanning trees on a given point set in the plane

Input:

A point set $P$ in the plane.

Output:

All plane spanning trees on $P$.

Complexity:

$O(|P|\log|P|)$ time per solution.

Comment:

Use gray code.

Reference:

[Aichholzer2007] (Bibtex)

P17: Enumeration of all plane graphs

Input:

$m$: the maximum number of edges.

Output:

All connected rooted plane graphs with at most $m$ edges.

Complexity:

amortized $O(1)$ time per graph with $O(m)$ space.

Comment:

This algorithm does not outputs the entire graph but the difference from previous one.

Reference:

[Yamanaka2009] (Bibtex)

P18: Enumeration of all plane graphs

Input:

$m$: the maximum number of edges.

Output:

All connected non-rooted plane graphs with at most $m$ edges.

Complexity:

$O(m^3)$ time per graph with $O(m)$ space.

Comment:

This algorithm does not outputs the entire graph but the difference from previous one.

Reference:

[Yamanaka2009] (Bibtex)

P248: Enumeration of all plane graphs on a given point set in the plane

Input:

A fixed point set $P$.

Output:

All plane graphs on $P$.

Complexity:

$O(N)$ total time.

Comment:

$N$ is the number of solutions.

Reference:

[Katoh2009a] (Bibtex)

P249: Enumeration of all non-crossing spanning connected graphs on a given point set in the plane

Input:

A fixed point set $P$.

Output:

All non-crossing spanning connected graphs on $P$.

Complexity:

$O(N)$ total time.

Comment:

$N$ is the number of solutions.

Reference:

[Katoh2009a] (Bibtex)

P250: Enumeration of all non-crossing spanning trees on a given point set in the plane

Input:

A fixed point set $P$.

Output:

All non-crossing spanning trees on $P$.

Complexity:

$O(N + |P|tri(P))$ total time.

Comment:

$N$ is the number of solutions and $tri(P)$ is the number of triangulations of $P$.

Reference:

[Katoh2009a] (Bibtex)

P251: Enumeration of all non-crossing minimally rigid frameworks on a given point set in the plane

Input:

A fixed point set $P$.

Output:

All non-crossing minimally rigid frameworks on $P$.

Complexity:

$O(|P|^2N)$ total time.

Comment:

$N$ is the number of solutions.

Reference:

[Katoh2009a] (Bibtex)

P252: Enumeration of all non-crossing perfect matchings on a given point set in the plane

Input:

A fixed point set $P$.

Output:

All non-crossing perfect matchings on $P$.

Complexity:

$O(|P|^{3/2}tri(P) + |P|^{5/2}N)$ total time.

Comment:

$N$ is the number of solutions and $tri(P)$ is the number of triangulations of $P$.

Reference:

[Katoh2009a] (Bibtex)

P208: Enumeration of all triconnected rooted plane graphs

Input:

Integers $n$ and $g$.

Output:

All triconnected rooted plane graphs with $n$ vertices, whose each inner face has the length at most $g$.

Complexity:

$O(1)$ delay with $O(n)$ space after $O(n)$ time preprocessing.

Comment:

Reference:

[Zhuang2010] (Bibtex)

P209: Enumeration of all triconnected rooted plane graphs

Input:

An integer $n$.

Output:

All triconnected rooted plane graphs with $n$ vertices.

Complexity:

$O(n^3)$ delay with $O(n)$ space after $O(n)$ time preprocessing.

Comment:

Reference:

[Zhuang2010] (Bibtex)

P215: Enumeration of all biconnected rooted plane graphs

Input:

Integers $n$ and $g$.

Output:

All biconnected rooted plane graphs with exactly $n$ vertices such that each inner face is of length at most $g$.

Complexity:

$O(1)$ delay with $O(n)$ space, after an $O(n)$ time preprocessing.

Comment:

Reference:

[Zhuang2010c] (Bibtex)

P216: Enumeration of all biconnected plane graphs

Input:

Integers $n$ and $g$.

Output:

All biconnected plane graphs with at most $n$ vertices such that each inner face is of length at most $g$.

Complexity:

$O(n^3)$ time per solution on average with $O(n)$ space.

Comment:

Reference:

[Zhuang2010c] (Bibtex)

P217: Enumeration of all biconnected rooted plane graphs

Input:

Integers $n$ and $g$.

Output:

All biconnected rooted plane graphs with at most $n$ vertices such that each inner face is of length at most $g$.

Complexity:

$O(1)$ delay with $O(n)$ space.

Comment:

Reference:

[Zhuang2010c] (Bibtex)

P219: Enumeration of all rooted plane graphs in $\mathcal{G}_{\text{int}}(n, g) - \mathcal{G}_3(n, g)$

Input:

Integers $n$ and $g$.

Output:

All rooted plane graphs in $\mathcal{G}_{\text{int}}(n, g) - \mathcal{G}_3(n, g)$

Complexity:

$O(1)$ delay with $O(n)$ space and time preprocessing.

Comment:

Reference:

[Zhuang2010a] (Bibtex)